/*
 ============================================================================
 Name        : Bakery.c
 Author      : Smadar
 Version     :
 Copyright   : Your copyright notice
 Description : Implementation of Bakery algorithm.
 ============================================================================
 */

//////////////////////////////////////////////////////////////////////////
//CAS
//////////////////////////////////////////////////////////////////////////
#if defined(__linux__) || defined(__linux) || defined(__gnu_linux__)
	//////////////////////////////////////////////////////////////////////////
	//types
	//////////////////////////////////////////////////////////////////////////
	typedef unsigned char      _u8;
	typedef unsigned short     _u16;
	typedef unsigned int       _u32;
	typedef unsigned long long _u64;
	typedef unsigned long long  tick_t;
	typedef _u32               ptr_t;
	#define CAS32(_a,_o,_n)         __sync_val_compare_and_swap ((_u32*)_a,(_u32)_o,(_u32)_n)
	#define MB()  __sync_synchronize()
	extern  tick_t RDTICK(void);
	#define RDTICK() \
        ({ tick_t __t; __asm__ __volatile__ ("rdtsc" : "=A" (__t)); __t; })
#elif defined(__sun__) || defined(__sun) || defined(sun)
	#include"sparc_defs_cc_TV.h"
#endif


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <math.h>
#include <time.h>

#define FREE_LOCK       1024

#define true 1
#define false 0
#define FREE_NODE -1

inline int max(long int a, long int b) {
  return a > b ? a : b;
}

typedef struct sharedData
{
	volatile unsigned long int*      number;
	volatile char*                   choosing;
	volatile tick_t         startTime;
	volatile tick_t         finishTime;
	volatile unsigned long int       countVisitInCS;
	volatile unsigned int   lock;
	volatile unsigned int   testMutualExclusion;
	volatile unsigned int   startClock;
	unsigned int                     numEnters;
        unsigned int               maxThreadNum;
	volatile char           flagStartClock;
	volatile char           flag;
}sharedData;

typedef struct thData
{
	sharedData*    sData;
	long int       counter;
	short int      id;
        char           padding[54];
}thData;

pthread_barrier_t bar;

void clearVar(sharedData* pSharedData)                     /* Free memory */
{

	pthread_barrier_destroy(&bar);

	if (pSharedData->number != NULL)
	{
		free((void*)pSharedData->number);

		pSharedData->number = NULL;
	}

	if (pSharedData->choosing != NULL)
	{
		free((void*)pSharedData->choosing);

		pSharedData->choosing = NULL;
	}


	free(pSharedData);

	pSharedData = NULL;
}

void test(const thData* data)                              // Test that only one process exist in critical section
{
	if(CAS32(&data->sData->testMutualExclusion, FREE_LOCK, data->id) != FREE_LOCK)
	{
		printf("\nError, mutual exclusion fail.\n");
	}

	CAS32(&data->sData->testMutualExclusion, data->id, FREE_LOCK);
}

void* threadRunBakery(void* ptr)                           // Bakery Algorithm for mutual exclusion
{

	int i, maxVal, l1, l2, l3, l4;
	/************** Initialized setting ******************/

	thData*              pThData        = (thData*)ptr;
	sharedData*          sData          = pThData->sData;
	volatile char*       choosing       = sData->choosing;
	volatile unsigned long int*   number         = sData->number;

	/************** All thread start to run together ******************/
//	pthread_barrier_wait(&bar);                        // Marked as comment when single process run alone

	if (CAS32(&sData->startClock, FREE_LOCK, 0) == FREE_LOCK) //Start time measuring
	{
		sData->startTime = RDTICK();
		sData->flagStartClock = false;
//		MB();
	}

	while(sData->flagStartClock)
	{}

	while(sData->flag)
	{

	/************** Entry code ****************************************/

		choosing[pThData->id] = true;

//		MB();

		maxVal = 0;

		for (i=0; i< sData->maxThreadNum; i+=4)
		{
			l1 = number[i];
			l2 = number[i+1];
			l3 = number[i+2];
			l4 = number[i+3];
                        maxVal = max(maxVal, max(max(l1, l2), max(l3, l4)));
		}

		number[pThData->id] = 1 + maxVal;

		choosing[pThData->id] = false;

//		MB();

		for (i=0; i< sData->maxThreadNum; i++)
		{
			while(choosing[i])
			{}

			while((number[i] > 0) && ((number[i] < number[pThData->id]) || ((number[i] == number[pThData->id]) && (i < pThData->id))))
					{}
		}

		/************** Critical section *******************************/

		sData->countVisitInCS++;

//		test(pThData);

		pThData->counter++;


		if(sData->countVisitInCS == sData->numEnters)
		{
			if (sData->flag)
			{
				//Stop time measuring
				sData->finishTime= RDTICK();
				sData->flag = 0;
//				MB();
			}

		}


		/************** Exit code **************************************/

		 number[pThData->id] = 0;

//		 MB();
	}

//	printf("%ld ",pThData->counter);

	if (pThData->id < sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

	return NULL;
}

void* threadWrite(void* ptr)                               //creating RMR's
{

	/************** Initialized setting ******************/

	thData*              pThData        = (thData*)ptr;
	sharedData*          sData          = pThData->sData;
	volatile char*       choosing       = pThData->sData->choosing;


	while(sData->flag)
	{

		choosing[0] = false;

	}


	if (pThData->id < sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

	return NULL;
}

sharedData* initalizeVar(int argc,char* argv[])            // Memory allocating and Initialize Data structures
{

	int i;

	size_t longIntSize = sizeof(long);

	sharedData* pSharedData = (sharedData*)malloc(sizeof(sharedData));

	pSharedData->maxThreadNum = 0;

	pSharedData->numEnters    = 0;


	if ( argc == 4 )
	{

		pSharedData->maxThreadNum = atoi(argv[2]);

		pSharedData->numEnters    = atoi(argv[3]);


		if (pSharedData->maxThreadNum < 1)
		{
			 printf("0 processes\n");
			 return NULL;
		}

		freopen (*++argv,"a",stdout);
	}

	printf("Bakery ");

	pSharedData->number    = (unsigned long*)malloc(pSharedData->maxThreadNum * longIntSize);

	pSharedData->choosing  = (char*)malloc(pSharedData->maxThreadNum * sizeof(char));

	for(i=0; i< pSharedData->maxThreadNum; i++)
	{
		pSharedData->number[i]   = 0;

		pSharedData->choosing[i] = false;

	}


	pthread_barrier_init(&bar, NULL, pSharedData->maxThreadNum);

	pSharedData->lock = FREE_LOCK;

	pSharedData->testMutualExclusion = FREE_LOCK;

	pSharedData->countVisitInCS = 0;

	pSharedData->flag = 1;

	pSharedData->flagStartClock = 1;

	pSharedData->startClock = FREE_LOCK;

	return pSharedData;
}


int main(int argc, char *argv[]) {

	int i;

	tick_t time;

	sharedData* pSharedData = initalizeVar(argc, argv);

	pthread_t*  threads     = (pthread_t*) malloc((pSharedData->maxThreadNum -1)* sizeof(pthread_t));

	thData*     tData       = (thData*)malloc(pSharedData->maxThreadNum * sizeof(thData));



	for(i=0; i<pSharedData->maxThreadNum ; i++)
	{
		tData[i].id        = i;
		tData[i].counter   = 0;
		tData[i].sData     = pSharedData;
//		if(i <pSharedData->maxThreadNum - 1)       // Marked as comments when single process run alone
//		{
//			pthread_create(&threads[i], NULL, threadRunBakery, &tData[i]);
//		}
	}

//	pthread_create(&threads[0], NULL, threadWrite, &tData[0]);  // Create process who cause RMRS in single process run
	threadRunBakery(&tData[pSharedData->maxThreadNum - 1]);
//	pthread_join(threads[0] , NULL);                            // Wait for process who cause RMR's to finish.

//	for(i=0; i<pSharedData->maxThreadNum - 1; i++)     // Marked as comments when single process run alone
//	{
//		pthread_join(threads[i] , NULL);
//	}

	time = pSharedData->finishTime - pSharedData->startTime;

	printf("%d %d %llu\n", pSharedData->maxThreadNum, pSharedData->numEnters,time);

	clearVar(pSharedData);

	free(threads);

	free(tData);

	fclose(stdout);


	return EXIT_SUCCESS;
}


